(1) Field of the Invention
The invention relates to a system reliability evaluation method for transmission by two minimal paths in time restriction, and especially relates to a system reliability evaluation method for transmission by two minimal paths of a stochastic-flow network in time restriction.
(2) Description of the Prior Art
With the diversification of the commodities and the information services, various kinds of the flow networks which value the transmission time, the flow and the budget has emerged, such as the computer system, the telecommunication system, the logistic system and the transportation system, etc. Hence, a time version of the shortest path problem, called the quickest path problem, is proposed in the fields of the information science, the operation research or the network planning. This problem is for finding a quickest path with the minimum transmission time to send a given amount of data from the start node to the terminal node. Since then, several variants of the quickest path problems are proposed: the constrained quickest path problem, the first k quickest paths problem, and all-pairs quickest path problem.
Two factors, the flow and the transmission time, are respectively processed in the conventional network analysis. For instance, the flow is processed in the maximum flow problem, the transmission time is processed to get the minimum transmission time in the shortest path problem. However, two factors, the transmission time and the flow, are simultaneously processed in the quickest path problem, and the transmission time is valued in the computer system and the telecommunication system.
Due to failure, partial failure, maintenance, etc., the capacity of each arc is stochastic in many real flow networks such as the computer, the telecommunication, the urban traffic, the logistics systems, etc. That is, each arc has several possible capacities or states. Such a network is named a stochastic-flow network. For instance, a computer system with the arcs denoting the transmission media and the nodes denoting stations of servers is a typical stochastic-flow network. In fact, each transmission medium is combined with several physical lines (the coaxial cables, the fiber optics, etc), and each physical line has only success or failure state. That implies a transmission medium has several states in which state k means k physical lines are successful.
Thus, in the computer network and the telecommunication network, the data can be transmitted through several disjoint minimal paths (MPs) simultaneously in order to reduce the transmission time and in several various factors, where a MP is an ordered sequence of arcs from the start node to the terminal node without loops. Namely, finding two MPs simultaneously transmitting data in time restriction is an important issue to conduct the system reliability evaluation method for a stochastic-flow network.